#include "seqlist.h"
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

/*
typedef struct seqlist {
  void *arr;    // 存储数据的连续内存
  int nmemb;    // 当前元素个数
  size_t size;  // 单个元素的大小
  int capacity; // 最大容量
} seqlist_t;
*/

// 初始化顺序表
int seqlist_init(seqlist_t **mylist, size_t elem_size, int init_capacity) {
  *mylist = malloc(sizeof(seqlist_t));
  if (*mylist == NULL) {
    return 0;
  }
  (*mylist)->arr = malloc(elem_size * init_capacity);
  if ((*mylist)->arr == NULL) {
    free(*mylist);
    *mylist = NULL;
    return 0;
  }
  (*mylist)->nmemb = 0;
  (*mylist)->size = elem_size;
  (*mylist)->capacity = init_capacity;
  return 1;
}

// 判断顺序表是否满
int seqlist_full(const seqlist_t *mylist) {
  if (mylist == NULL) {
    return -1;
  }
  return mylist->nmemb == mylist->capacity;
}

// 判断顺序表是否空
int seqlist_empty(const seqlist_t *mylist) {
  if (mylist == NULL) {
    return -1;
  }
  return mylist->nmemb == 0;
}

// 在表尾添加元素
int seqlist_push_back(seqlist_t *mylist, const void *newdata) {
  if (mylist == NULL || newdata == NULL) {
    return -1;
  }
  if (seqlist_full(mylist)) {
    int new_capacity = mylist->capacity * 2;
    if (seqlist_resize(&mylist, new_capacity) == -1) {
      return -1;
    }
    // return -1;
  }
  return seqlist_insert(mylist, mylist->nmemb, newdata);
}

// 在指定位置插入元素
int seqlist_insert(seqlist_t *mylist, int index, const void *newdata) {
  if (mylist == NULL || newdata == NULL || index < 0 ||
      index > mylist->capacity) {
    return -1;
  }
  if (seqlist_full(mylist)) {
    int new_capacity = mylist->capacity * 2;
    if (seqlist_resize(&mylist, new_capacity) == -1) {
      return -1;
    }
  }
  if (index == mylist->nmemb) {
    memcpy((char *)mylist->arr + index * mylist->size, newdata, mylist->size);
  } else {
    memmove((char *)mylist->arr + (index + 1) * mylist->size,
            (char *)mylist->arr + index * mylist->size,
            (mylist->nmemb - index) * mylist->size);
    memcpy((char *)mylist->arr + index * mylist->size, newdata, mylist->size);
  }
  mylist->nmemb++;
  return 1;
}

// 按 key 删除第一个匹配的元素
int seqlist_delete(seqlist_t *mylist, const void *key, seqlist_cmp_t cmp) {
  if (mylist == NULL || key == NULL) {
    return -1;
  }
  char *ptr = (char *)seqlist_forsearch(mylist, key, cmp);
  if (ptr == NULL) {
    return -1;
  }
  memmove(ptr, ptr + mylist->size,
          ((char *)mylist->arr + (mylist->nmemb - 1) * mylist->size - ptr) /
              mylist->size);
  mylist->nmemb--;
  return 1;
}

// 按 key 更新第一个匹配的元素
int seqlist_update(seqlist_t *mylist, const void *key, const void *newdata,
                   seqlist_cmp_t cmp) {
  if (mylist == NULL || key == NULL || newdata == NULL) {
    return -1;
  }
  void *ptr = seqlist_forsearch(mylist, key, cmp);
  if (ptr == NULL) {
    return -1;
  }
  memcpy(ptr, newdata, mylist->size);
  return 1;
}

// 按 key 查找第一个匹配的元素
void *seqlist_forsearch(const seqlist_t *mylist, const void *key,
                        seqlist_cmp_t cmp) {
  if (mylist == NULL || key == NULL) {
    return NULL;
  }
  char *ptr = (char *)mylist->arr;
  char *end = (char *)mylist->arr + (mylist->nmemb - 1) * mylist->size;
  while (ptr <= end) {
    if (cmp(ptr, key) == 0) {
      break;
    } else {
      ptr += mylist->size;
    }
  }
  return ptr > end ? NULL : ptr;
}

// 遍历所有元素
void seqlist_traval(const seqlist_t *mylist, seqlist_traval_t traval) {
  for (int i = 0; i < mylist->nmemb; i++) {
    traval(mylist->arr + i * mylist->size);
  }
}

// 销毁顺序表
void seqlist_destory(seqlist_t **mylist) {
  if (*mylist == NULL) {
    return;
  }
  if ((*mylist)->arr != NULL) {
    free((*mylist)->arr);
    (*mylist)->arr = NULL;
  }
  free(*mylist);
  *mylist = NULL;
}

// 获取当前元素个数
int seqlist_size(const seqlist_t *mylist) {
  if (mylist == NULL) {
    return -1;
  }
  return mylist->nmemb;
}

// 获取容量
int seqlist_capacity(const seqlist_t *mylist) {
  if (mylist == NULL) {
    return -1;
  }
  return mylist->capacity;
}

// 获取 index 位置的元素
const void *seqlist_get(const seqlist_t *mylist, int index) {
  if (mylist == NULL || index > mylist->nmemb - 1) {
    return NULL;
  }
  return (char *)mylist->arr + index * mylist->size;
}

// 修改 index 位置的元素
int seqlist_set(seqlist_t *mylist, int index, const void *newdata) {
  if (mylist == NULL || index > mylist->nmemb - 1) {
    return -1;
  }
  memcpy((char *)mylist->arr + index * mylist->size, newdata, mylist->size);
  return 1;
}

// 清空所有元素
void seqlist_clear(seqlist_t *mylist) {
  if (mylist == NULL) {
    return;
  }
  memset(mylist->arr, 0, mylist->size * mylist->nmemb);
  mylist->nmemb = 0;
}

// 调整容量
int seqlist_resize(seqlist_t **mylist, int new_capacity) {
  void *new_arr = malloc(new_capacity * (*mylist)->size);
  if (new_arr == NULL) {
    free(new_arr);
    new_arr = NULL;
    return -1;
  }
  void *temp = (*mylist)->arr;
  memcpy(new_arr, (*mylist)->arr, (*mylist)->size * (*mylist)->nmemb);
  (*mylist)->arr = new_arr;
  free(temp);
  (*mylist)->capacity = new_capacity;
  return 1;
}

static void __swap(void *a, void *b, size_t size) {
  void *temp = malloc(size);
  if (temp == NULL) {
    return;
  }
  memcpy(temp, a, size);
  memcpy(a, b, size);
  memcpy(b, temp, size);
  free(temp);
}

// 快速排序
int seqlist_qsort(void *base, size_t nmemb, size_t size, seqlist_cmp_t cmp) {
  if (base == NULL || cmp == NULL) {
    return -1;
  }
  if (nmemb <= 1) {
    return 1;
  }
  char *ptr_base = malloc(size);
  memcpy(ptr_base, base, size);
  char *left = (char *)base;
  char *right = (char *)base + (nmemb - 1) * size;
  while (left < right) {
    while (left < right && cmp(ptr_base, right) <= 0) {
      right -= size;
    }
    while (left < right && cmp(left, ptr_base) < 0) {
      left += size;
    }
    if (left < right)
      __swap(left, right, size);
  }
  __swap(base, left, size);
  size_t l_nmemb = (left - (char *)base) / size;
  size_t r_nmemb = nmemb - l_nmemb - 1;
  free(ptr_base);
  seqlist_qsort(base, l_nmemb, size, cmp);
  seqlist_qsort(left + size, r_nmemb, size, cmp);

  return 1;
}

void *seqlist_bsearch(void *key, seqlist_t *mylist, seqlist_cmp_t cmp) {
  char *left = mylist->arr;
  char *right = mylist->arr + (mylist->nmemb - 1) * mylist->size;
  char *mid;
  while (left <= right) {
    mid = mylist->arr + (mylist->nmemb - 1) / 2 * mylist->size;
    if (cmp(mid, key) == 0) {
      return mid;
    } else {
      if (cmp(mid, key) > 0) {
        right = mid - mylist->size;
      } else {
        left = mid + mylist->size;
      }
    }
  }
  return NULL;
}

int seqlist_reverse(seqlist_t *mylist) {
  for (char *i = (char *)mylist->arr,
            *j = (char *)mylist->arr + mylist->size * (mylist->nmemb - 1);
       i < j; i += mylist->size, j -= mylist->size) {
    __swap(i, j, mylist->size);
  }
  return 1;
}

int seqlist_init_by_list(seqlist_t **newlist, const seqlist_t srclist) {
  *newlist = malloc(sizeof(seqlist_t));
  if (*newlist == NULL) {
    return -1;
  }
  (*newlist)->arr = malloc(srclist.size * srclist.capacity);
  if ((*newlist)->arr == NULL) {
    free(*newlist);
    (*newlist) = NULL;
    return -1;
  }
  memcpy((*newlist)->arr, srclist.arr, srclist.size * (srclist.nmemb - 1));
  (*newlist)->size = srclist.size;
  (*newlist)->nmemb = srclist.nmemb;
  (*newlist)->capacity = srclist.capacity;
  return 1;
}

int seqlist_new_reverse(seqlist_t **newlist, const seqlist_t srclist) {
  if (seqlist_init_by_list(newlist, srclist) == -1) {
    return -1;
  }
  seqlist_reverse(*newlist);
  return 1;
}
